package com.company.chu;

public class Sort {

    public static void main(String[] args) {
        int[] nums = {9,8,7,6,5,4,3,2,1};
       // bubbleSort(nums);
       // insertionSort(nums);
       // mergeSort(nums);
        quickSort(nums);
        for (int i :nums) {
            System.out.print(i+",");
        }
    }


    // 冒泡排序
    static void bubbleSort(int [] nums){
        int len = nums.length;
        int temp;
        for (int i = 0;i<len-1;i++){
            for (int j = i+1;j<len;j++){
                if(nums[i]>nums[j]){
                    temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        System.out.println("冒泡排序后的数组是");
        for (int i :nums) {
            System.out.print(i+",");
        }
    }

   // 插入排序
    static void insertionSort(int[] nums){
        for (int i = 1;i<nums.length;i++){
            int value = nums[i];
            int j = i -1;
            for (;j>=0;j--){
                if(nums[j]>value){
                    nums[j+1] = nums[j] ;
                }else {
                    break;
                }
            }
            nums[j+1] = value;
        }
        System.out.println("插入排序后的数组是");
        for (int i :nums) {
            System.out.print(i+",");
        }
    }

    // 归并排序
    static void mergeSort(int[]nums){
        int[] temp = new int[nums.length];
        merge(nums,0,nums.length-1,temp);

    }
    static void merge(int[] nums,int left,int right,int[]temp){
        if(left<right){
            int mid = (left+right) /2;
            merge(nums,left,mid,temp);
            merge(nums,mid+1,right,temp);
            heBing(nums,left,mid,right,temp);
        }
    }

    static void heBing(int[] nums ,int left,int mid ,int right,int[]temp){
        int i = left;
        int j = mid +1;
        int t = 0;
        while (i<= mid &&j<=right) {
            if (nums[i] < nums[j]) {
                temp[t++] = nums[i++];
            } else {
                temp[t++] = nums[j++];
            }
        }
            while (i<=mid){
                temp[t++] = nums[i++];
            }
            while (j<=right){
                temp[t++] = nums[j++];
            }
            t = 0;
            //将temp中的元素全部拷贝到原数组中
            while(left <= right){
                nums[left++] = temp[t++];
            }

        }



    //快速排序
        static void quickSort(int[] nums){
            quick(nums,0,nums.length-1);
        }



        static void quick(int[] arr,int low,int high) {
            int i,j,temp,t;
            if(low>high){
                return;
            }
            i=low;
            j=high;
            //temp就是基准位
            temp = arr[low];

            while (i<j) {
                //先看右边，依次往左递减
                while (temp<=arr[j]&&i<j) {
                    j--;
                }
                //再看左边，依次往右递增
                while (temp>=arr[i]&&i<j) {
                    i++;
                }
                //如果满足条件则交换
                if (i<j) {
                    t = arr[j];
                    arr[j] = arr[i];
                    arr[i] = t;
                }

            }
            //最后将基准为与i和j相等位置的数字交换
            arr[low] = arr[i];
            arr[i] = temp;
            //递归调用左半数组
            quick(arr, low, j-1);
            //递归调用右半数组
            quick(arr, j+1, high);

        }
}
